/*
*
给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。
示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length <= 600
1 <= strs[i].length <= 100
strs[i] 仅由 '0' 和 '1' 组成
1 <= m, n <= 100

  - @author ala
  - @date 2024-10-09 13:18
*/
package main

import "fmt"

func main() {
	strs := []string{"10", "0001", "111001", "1", "0"}
	m, n := 5, 3

	//strs := []string{"10", "0", "1"}
	//m, n := 1, 1

	fmt.Println(findMaxForm(strs, m, n))
}

func findMaxForm(strs []string, m int, n int) int {
	//return V1(strs, m, n)
	return V2(strs, m, n)
}

/**
 *	1）dp[i][j][k]表示前i个字符，凑出j个0，k个1用掉的字符数
 *	2）第i个字符可用可不用
 *		不用：dp[i][j][k] = dp[i-1][j][k]
 *		用：  dp[i][j][k] = dp[i-1][j - z][k - o]
 *		其中：z o 表示第 i 个字符串中 0 的数量和 1 的数量
 */
func V1(strs []string, m int, n int) int {
	N := len(strs)
	dp := make([][][]int, N+1)
	for i := range dp {
		dp[i] = make([][]int, m+1)
		for j := range dp[i] {
			dp[i][j] = make([]int, n+1)
		}
	}

	for i := 1; i <= N; i++ {
		z, o := zm(strs[i-1])
		for j := 0; j <= m; j++ {
			for k := 0; k <= n; k++ {
				dp[i][j][k] = dp[i-1][j][k]
				if j >= z && k >= o {
					dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-z][k-o]+1)
				}
			}
		}
	}

	return dp[N][m][n]
}

/**
 *	滚动数组版本
 */
func V2(strs []string, m, n int) int {
	dp := make([][]int, m+1)
	for j := range dp {
		dp[j] = make([]int, n+1)
	}

	for _, s := range strs {
		z, o := zm(s)
		for j := m; j >= 0; j-- {
			for k := n; k >= 0; k-- {
				if j >= z && k >= o {
					dp[j][k] = dp[j-z][k-o] + 1
				}
			}
		}
	}
	return dp[m][n]
}

func zm(s string) (int, int) {
	m, n := 0, 0
	for i := range s {
		if s[i] == '0' {
			m++
		} else {
			n++
		}
	}
	return m, n
}
